package 练习题;

/**
 * @author Liangyaoyun
 */
public class MyDoubleLinkedList {

    /**
     双链表节点内部类
     */
    private static class Node {
        Object data;  //数据域
        Node prev;  //前驱指针域
        Node next;  //后继指针域
    }

    //创建双链表的头尾指针
    private Node head = new Node();
    private Node tail = new Node();

    //表示链表中保存数据节点数量的全局变量
    private int size;

    /**
     在构造器中对头尾节点进行初始化关联
     */
    public MyDoubleLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    /**
     按照下标获取双链表中保存的元素
     */
    public Object get(int index) {

        //1.判断目标下标是否越界
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("链表下标越界：" + index);
        }

        //2.计算判断目标下标距离哪一端更近并进行遍历
        int step;  //计步器变量
        Node current;  //指向链表中被遍历节点的临时变量
        if(index < size / 2) {
            //2.1如果目标下标距离头节点一端更近
            step = -1;
            current = head;
            while(step < index) {
                current = current.next;
                step++;
            }
            //循环结束后，current变量指向下标为index的节点
        } else {
            //2.2如果目标下标距离尾节点一端更近
            step = size;
            current = tail;
            while(step > index) {
                current = current.prev;
                step--;
            }
            //循环结束后，current变量指向下标为index的节点
        }

        //3.返回目标下标节点的数据域取值
        return current.data;

    }

    /**
     在双链表中向指定下标位添加新元素的方法
     */
    public void insert(int index, Object data) {

        //1.判断目标下标是否越界
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("链表下标越界：" + index);
        }

        //2.创建新节点保存新元素
        Node node = new Node();
        node.data = data;

        //3.通过双端计步器法定位插入下标位的前驱节点
        int step;  //计步器变量
        Node current;  //指向链表中被遍历节点的临时变量
        if(index-1 < size / 2) {
            //3.1如果目标下标距离头节点一端更近
            step = -1;
            current = head;
            while(step < index-1) {
                current = current.next;
                step++;
            }
            //循环结束后，current变量指向插入位置的前驱节点
        } else {
            //3.2如果目标下标距离尾节点一端更近
            step = size;
            current = tail;
            while(step > index-1) {
                current = current.prev;
                step--;
            }
            //循环结束后，current变量指向插入位置的前驱节点
        }

        //4.执行节点插入操作
        current.next.prev = node;
        node.next = current.next;

        current.next = node;
        node.prev = current;

        //5.元素数量自增
        size++;

    }

    /**
     删除双链表中指定下标位元素的方法
     */
    public Object remove(int index) {

        //1.判断目标下标是否越界
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("链表下标越界：" + index);
        }

        //2.通过双端计步器法定位删除下标位的节点
        int step;  //计步器变量
        Node removedNode;  //指向链表中被遍历节点的临时变量
        if(index < size / 2) {
            //2.1如果目标下标距离头节点一端更近
            step = -1;
            removedNode = head;
            while(step < index-1) {
                removedNode = removedNode.next;
                step++;
            }
            //循环结束后，removedNode变量指向删除位置的节点
        } else {
            //2.2如果目标下标距离尾节点一端更近
            step = size;
            removedNode = tail;
            while(step > index-1) {
                removedNode = removedNode.prev;
                step--;
            }
            //循环结束后，removedNode变量指向删除位置的节点
        }

        //3.定位被删除节点的前驱节点和后继节点，执行节点删除操作
        Node removedPrev = removedNode.prev;
        Node removedNext = removedNode.next;

        removedPrev.next = removedNext;
        removedNext.prev = removedPrev;

        //4.元素数量自减，返回被删除节点数据域取值
        size--;
        return removedNode.data;

    }
    private int length(int size){
        this.size=size;
        return size;
    }


}
